package solution;

class Solution {

    /**
     * 9、回文数
     * https://leetcode.cn/problems/palindrome-number/
     */
    //数学，判断首位和末尾
    public boolean isPalindrome2(int x) {
        if(x < 0) {
            return false;
        }
        //数学，每次都拿第一位和最后一位进行比较
        int tmp = x;
        int help = 1;
        while(tmp >= 10) {
            help *= 10;
            tmp /= 10;
        }
        while(x != 0) {
            if((x / help) != (x % 10)) {
                return false;
            }
            x = x % help / 10;
            help /= 100;
        }
        return true;
    }
    //双指针
    public boolean isPalindrome(int x) {
        String str = String.valueOf(x);
        int [] arr = new int[str.length()];
        for(int i = 0; i < str.length(); i++) {
            arr[i] = str.charAt(i);
        }
        int right = 0;
        int left = str.length() - 1;
        while(right < left) {
            if(arr[right] != arr[left]) {
                return false;
            }
            right++;
            left--;
        }
        return true;
    }

    /**
     * 470用rand7()实现rand10()
     * https://leetcode.cn/problems/implement-rand10-using-rand7/description/
     */
    public static int rand7() {
        return 0;
    }
    public int rand10() {
        int tmp = (rand7() - 1) * 7 + rand7();
        while(tmp > 40) {
            tmp = (rand7() - 1) * 7 + rand7();
        }
        //不是41到49,1到40之间是等概率的
        return (tmp - 1) % 10 + 1;
    }
    /**
     * 53最大子数组和
     * https://leetcode.cn/problems/maximum-subarray/description/
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        //动态规划
        int[] dp = new int[nums.length];//放i下标最大连续数组的和
        dp[0] = nums[0];
        int result = dp[0];
        //遍历一遍num数组，算出当前下标值 + dp数组前一个下标值，和当前下标值比，谁大放进dp数组中
        for(int i = 1; i < nums.length; i++) {
            dp[i] = nums[i] > (nums[i] + dp[i - 1]) ? nums[i] : (nums[i] + dp[i - 1]);
            if(result < dp[i]) {
                result = dp[i];
            }
        }
        return result;
    }
}